package airthmetic.exercise.dp;

import java.util.Arrays;

public class _198_打家劫舍 {

    /*
    你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

    给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。


    示例 1：

    输入：[1,2,3,1]
    输出：4
    解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
         偷窃到的最高金额 = 1 + 3 = 4 。
    示例 2：

    输入：[2,7,9,3,1]
    输出：12
    解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     */
    public int rob(int[] nums) {
        /*
        * 1.确定状态参数/选择和决策
        *   状态是原问题和子问题之间变化的值 这里是nums的index
        *   选择/决策 选择/决策是使状态参数变化并趋近于原问题   这里是nums的index
        * 2.定义dp数组(dp table)的含义
        *   这里nums[i]被作为选择，能偷窃最多的现金 即 nums[i] = dp[i]
        * 3.初始状态参数定义
        *   这里可以给当前index的值，也可以是0
        * 4.推导状态转移(状态转移公式)
        *   动态规划状态转移的核心是，根据子问题的解推导原问题
        *   状态转移 dp[0],dp[1]...dp[i-2],dp[i-1]的值，推导 dp[i]
        *   dp[i] = Math.max(dp[i], dp[j] + nums[i]);
        *
        *
        *
        *
        * */
        if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return nums[0] > nums[1] ? nums[0] : nums[1];
        }

        int[] dp = new int[nums.length];
        for(int i=0; i< nums.length; i++){
            dp[i] = nums[i];
        }

        int max = 0;
        for(int i=0; i < nums.length; i++){
            for(int j=0; j<i-1; j++){
                dp[i] = Math.max(dp[i], dp[j] + nums[i]);
            }

            max = Math.max(max, dp[i]);
        }
        return max;
    }

    // 动态规划
    public int rob2(int[] nums) {
        /**
         因为问题存在重叠子问题和无后效性以及最优子结构。 动态规划！
         重叠子问题：偷盗dp[i-1] , dp[i-2] 在dp[i-1] 与dp[i-2]基础上加上dp[i]
         无后效性：偷盗dp[i]不会因为后续继续偷盗而改变最多能偷盗的金额
         最优子结构：偷盗dp[i-1] , dp[i-2]是最优能偷金额，能被后续问题使用

         动态规划思考问题：
         1.确定状态参数和选择
         先思考原问题与子问题
         原问题：偷盗dp[0]
         子问题：偷盗dp[0+1]  偷盗dp[0+2]

         状态参数：偷盗的最大金额

         选择/决策: 选择偷盗哪件房间

         2.定义dp table 数组
         int[] dp = new int[nums.length + 2];
         dp[i]表示从i开始偷盗最多能偷到多少金额
         3.初始化dp table
         dp[nums.length - 1] = 0;
         dp[nums.length ] = 0;
         dp[nums.length + 1] = 0;

         4.推导状态转移公式
         dp[i] = Math.max(nums[i]+ dp[i+2], dp[i+1]);
         */

        int[] dp = new int[nums.length + 2];
        dp[nums.length - 1] = 0;
        dp[nums.length ] = 0;
        dp[nums.length + 1] = 0;

        for(int i=nums.length -1; i>=0; i--){
            dp[i] = Math.max(nums[i]+ dp[i+2], dp[i+1]);
        }

        return dp[0];

    }


    // 状态压缩动态规划
    public int rob3(int[] nums) {
        /**
         因为问题存在重叠子问题和无后效性以及最优子结构。 动态规划！
         重叠子问题：偷盗dp[i-1] , dp[i-2] 在dp[i-1] 与dp[i-2]基础上加上dp[i]
         无后效性：偷盗dp[i]不会因为后续继续偷盗而改变最多能偷盗的金额
         最优子结构：偷盗dp[i-1] , dp[i-2]是最优能偷金额，能被后续问题使用

         动态规划思考问题：
         1.确定状态参数和选择
         先思考原问题与子问题
         原问题：偷盗dp[0]
         子问题：偷盗dp[0+1]  偷盗dp[0+2]

         状态参数：偷盗的最大金额

         选择/决策: 选择偷盗哪件房间

         2.定义dp table 数组
         int[] dp = new int[nums.length + 2];
         dp[i]表示从i开始偷盗最多能偷到多少金额
         3.初始化dp table
         dp[nums.length - 1] = 0;
         dp[nums.length ] = 0;
         dp[nums.length + 1] = 0;

         4.推导状态转移公式
         dp[i] = Math.max(nums[i]+ dp[i+2], dp[i+1]);
         */

        //  int[] dp = new int[nums.length + 2];
        //  dp[nums.length - 1] = 0;
        //  dp[nums.length ] = 0;
        //  dp[nums.length + 1] = 0;

        int n = 0;
        int n_1 = 0;
        int n_2 = 0;
        for(int i=nums.length-1; i>=0; i--){
            n = Math.max(nums[i]+ n_2, n_1);
            n_2 =  n_1;
            n_1 = n;

        }

        return n;

    }

    // 状态压缩
    public int rob4(int[] nums) {
        int m = nums.length;

        int dp_0 = 0;
        int dp_0_1 = 0;
        int dp_0_2 = 0;

        for(int i=m - 1; i>=0; i--){
            dp_0 = Math.max(dp_0_1, nums[i] + dp_0_2);
            dp_0_2 = dp_0_1;
            dp_0_1 = dp_0;
        }

        return dp_0;
    }


}
